package demo6;

/**
 * 给定一棵二叉树的头节点head，和另外两个节点a和b，返回a和b的最低公共祖先
 */

public class TestDemo {

    //二叉树节点
    static class TreeNode{
        public int data;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int data){
            this.data = data;
        }
    }

    static class Info{
        public boolean findA;//找到A了没
        public boolean findB;//找到B了没
        public TreeNode ans;//找到答案了没

        public Info(boolean findA,boolean findB,TreeNode ans){
            this.findA = findA;
            this.findB = findB;
            this.ans = ans;
        }
    }

    public static TreeNode lowestAncestor(TreeNode head,TreeNode a,TreeNode b){
         if(head==null) return null;
         return process(head,a,b).ans;
    }

    public static Info process(TreeNode head,TreeNode a,TreeNode b){
        if(head==null) return new Info(false,false,null);

        Info leftInfo = process(head.left,a,b);
        Info rightInfo = process(head.right,a,b);
        boolean findA = leftInfo.findA || rightInfo.findA || head==a;
        boolean findB = leftInfo.findB || rightInfo.findB || head==b;
        TreeNode ans = null;
        if(leftInfo.ans!=null){
            ans = leftInfo.ans;
        }else if(rightInfo.ans!=null){
            ans = rightInfo.ans;
        }else {
            if(findA&&findB){
                ans = head;
            }
        }

        return new Info(findA,findB,ans);
    }


    public static void main(String[] args) {

    }

}
